package class001_010;

/**
 * ClassName: Code04_SelectBubbleInsert
 * Package: class001_010
 * Description:
 *
 * @Author s
 * @Create 2025/7/24 15:56
 * @Version 1.0
 */
public class Code04_SelectBubbleInsert {
    public static void main(String[] args) {
        int[] arr = {13, 6, 16, 81 ,1, 4, 12,  64, 12, 2};
        printArr(arr);

//        selectionSort(arr);
//        printArr(arr);

        bubbleSort(arr);
        printArr(arr);


    }
    public static void printArr(int[] arr) {
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + " ");
        }
        System.out.println();
    }
    public static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }


    // TODO 选择排序
    public static void selectionSort(int[] arr) {
        if(arr == null || arr.length < 2) {
            return;
        }

        // 5 2 1 4 3
        // 0 1 2 3 4

        // i < arr.length - 1   i < 5 - 1 = 4   i < 4   0 1 2 3
        // 5个数字，只需要确定4轮最小值，剩下一个数一定是最大的，所以边界值取i < arr.length - 1

        // j < arr.length                       j < 5   0 1 2 3 4
        // 最后一轮只剩两个数，j要取到最后一个数字，所以j < arr.length
        for (int minIndex, i = 0; i < arr.length - 1; i++) {
            minIndex = i;
            for (int j = i + 1; j < arr.length; j++) {
                if(arr[j] < arr[minIndex]) {
                    minIndex = j;
                }
            }
            swap(arr, i, minIndex);

        }
    }
    
    // 冒泡排序
    public static void bubbleSort(int[] arr) {
        if(arr == null || arr.length < 2) {
            return;
        }

        // 5 2 1 4 3
        // 0 1 2 3 4
        // 冒泡排序，每轮沉下去一个，最后一个自然有序，所以只需要进行长度 - 1 轮
        // i < arr.length - 1      i < 4   0 1 2 3   四轮
        // i = 0   j < 5 - 0 - 1     j < 4   0 1 2 3
        // i = 1   j < 5 - 1 - 1     j < 3   0 1 2
        // i = 2   j < 5 - 2 - 1     j < 2   0 1
        // i = 3   j < 5 - 3 - 1     j < 1   0

        for (int i = 0; i < arr.length - 1; i++) {
            for (int j = 0; j < arr.length - i - 1; j++) {
                if (arr[j] > arr[j + 1]) {
                    swap(arr, j, j + 1);
                }
            }
        }

    }

    // 插入排序
    public static void insertionSort(int[] arr) {
        if(arr == null || arr.length < 2) {
            return;
        }

        // 5 2 1 4 3
        // 0 1 2 3 4
        // i < 5   i = 1, 2, 3, 4
        // i = 1   j = 0                        2 5 1 4 3
        // i = 2   j = 1, 0                     2 1 5 4 3   1 2 5 4 3
        // i = 3   j = 2, 1, 0                  1 2 4 5 3
        // i = 4   j = 3, 2, 1, 0               1 2 4 3 5   1 2 3 4 5
        for(int i = 1; i < arr.length; i++) {
            for(int j = i - 1; j >= 0 && arr[j] > arr[j + 1]; j--) {
                swap(arr, j, j + 1);
            }
        }
    }
}
